#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ep emplace
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;
using tl = tuple < int, int, int >;

const int N = 1e6 + 10;
const int M = 1e5 + 10;

char s[N];
int nxt[N], ans[M], x[M], y[M], n, fa[N], m;
bool vis[N];
vec G[N];
veg ques[N];

int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }

void dfs(int x) {
	vis[x] = true; fa[x] = x;
	for(auto y : ques[x]) if(vis[y.fi]) ans[y.se] = gf(y.fi);
	for(auto y : G[x]) if(!vis[y]) dfs(y), fa[y] = x;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	scanf("%s", s + 1); n = strlen(s + 1); m = in;
	int j = 0;
	rep(i, 2, n) {
		while(j && s[j + 1] != s[i]) j = nxt[j];
		if(s[j + 1] == s[i]) j++;
		nxt[i] = j;
	}
	rep(i, 1, n) G[nxt[i]].eb(i);
	rep(i, 1, m) x[i] = in, y[i] = in, ques[x[i]].eb(y[i], i), ques[y[i]].eb(x[i], i);
	dfs(0);
	rep(i, 1, m) printf("%d\n", ans[i] == x[i] || ans[i] == y[i] ? nxt[ans[i]] : ans[i]);
	return 0;
}
